SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Amorphous computing</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Amorphous computing</span></span>

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p><b>Amorphous computing</b> refers to computational systems that use very large numbers of identical, parallel processors each having limited computational ability and local interactions. The term <i>amorphous computing</i> was coined at MIT in 1996 in a paper entitled <a rel="nofollow" class="external text" href="http://www-swiss.ai.mit.edu/projects/amorphous/white-paper/amorph-new/amorph-new.html">"Amorphous Computing Manifesto"</a> by Abelson, Knight, Sussman, et al.

</p><p>Examples of naturally occurring amorphous computations can be found in many fields, such as <a href="Developmental_biology" title="Developmental biology">developmental biology</a> (the development of multicellular organisms from a single cell), <a href="Molecular_biology" title="Molecular biology">molecular biology</a> (the organization of sub-cellular compartments and intra-cell signaling), <a href="Neural_networks" class="mw-redirect" title="Neural networks">neural networks</a>, and <a href="Chemical_engineering" title="Chemical engineering">chemical engineering</a> (non-equilibrium systems). The study of amorphous computation is <i>hardware agnostic</i>—it is not concerned with the physical substrate (biological, electronic, nanotech, etc.) but rather with the characterization of amorphous algorithms as abstractions with the goal of both understanding existing natural examples and engineering novel systems. Ultimately, this field extenuates to <a href="Computational_intelligence" title="Computational intelligence">Computational Intelligence</a>, as this computational technique is an extenuation of <a href="Artificial_intelligence" title="Artificial intelligence">Artificial Intelligence</a> (but more specifically <a href="Artificial_general_intelligence" title="Artificial general intelligence">Artificial General Intelligence</a>) for developing <a href="Biological_computation" title="Biological computation">Biological Computation</a>.

</p><p>Amorphous computers tend to have many of the following properties:

</p>

<ul><li>Implemented by redundant, potentially faulty, <a href="Massively_parallel" title="Massively parallel">massively parallel</a> devices.</li>

<li>Devices having limited memory and computational abilities.</li>

<li>Devices being asynchronous.</li>

<li>Devices having no <i>a priori</i> knowledge of their location.</li>

<li>Devices communicating only locally.</li>

<li>Exhibit emergent or self-organizational behavior (patterns or states larger than an individual device).</li>

<li>Fault-tolerant, especially to the occasional malformed device or state perturbation.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Algorithms,_tools,_and_patterns">Algorithms, tools, and patterns</h2></div>

<p>(Some of these algorithms have no known names. Where a name is not known, a descriptive one is given.)

</p>

<ul><li><b>"Fickian communication"</b>. Devices communicate by generating messages which diffuse through the medium in which the devices dwell. Message strength will follow the inverse square law as described by <a href="Fick's_law_of_diffusion" class="mw-redirect" title="Fick's law of diffusion">Fick's law of diffusion</a>. Examples of such communication are common in biological and chemical systems.</li>

<li><b>"Link diffusive communication"</b>. Devices communicate by propagating messages down links wired from device to device. Unlike "Fickian communication", there is not necessarily a diffusive medium in which the devices dwell and thus the spatial dimension is irrelevant and <a href="Fick's_law_of_diffusion" class="mw-redirect" title="Fick's law of diffusion">Fick's law</a> is not applicable. Examples are found in Internet routing algorithms such as the <a href="Diffusing_update_algorithm" title="Diffusing update algorithm">diffusing update algorithm</a>. Most algorithms described in the amorphous computing literature assume this kind of communication.</li>

<li><b>"Wave Propagation"</b>. (Ref 1) A device emits a message with an encoded hop-count. Devices which have not seen the message previously, increment the hop count, and re-broadcast. A wave propagates through the medium and the hop-count across the medium will effectively encode a distance gradient from the source.</li>

<li><b>"Random ID"</b>. Each device gives itself a random id, the random space being sufficiently large to preclude duplicates.</li>

<li><b>"Growing-point program"</b>. (Coore). Processes that move among devices according to 'tropism' (movement of an organism due to external stimuli).</li>

<li><b>"Wave coordinates"</b>. <a rel="nofollow" class="external text" href="http://groups.csail.mit.edu/mac/projects/amorphous/tucson-talk/">DARPA PPT slides</a>. To be written.</li>

<li><b>"Neighborhood query"</b>. (Nagpal) A device samples the state of its neighbors by either a push or pull mechanism.</li>

<li><b>"Peer-pressure"</b>. Each device maintains a state and communicates this state to its neighbors. Each device uses some voting scheme to determine whether or not to change state to its neighbor's state. The algorithm partitions space according to the initial distributions and is an example of a clustering algorithm.</li>

<li><b>"Self maintaining line"</b>. (<a rel="nofollow" class="external text" href="http://www-swiss.ai.mit.edu/projects/amorphous/Robust/laurenc/amorphous/self-repair.html">Lauren Lauren, Clement</a>). A gradient is created from one end-point on a plane covered with devices via Link Diffusive Communication. Each device is aware of its value in the gradient and the id of its neighbor that is closer to the origin of the gradient. The opposite end-point detects the gradient and informs its closer neighbor that it is part of a line. This propagates up the gradient forming a line which is robust against disruptions in the field. (Illustration needed).</li>

<li><b>"Club Formation"</b>. (<a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/cache/papers/cs/2546/http:zSzzSzswissnet.ai.mit.eduzSz~switzzSzamorphouszSzpaperszSzaimemo1614.pdf/coore97paradigms.pdf">Coore, Coore, Nagpal, Weiss</a>). Local clusters of processors elect a leader to serve as a local communication hub.</li>

<li><b>"Coordinate formation"</b> (<a rel="nofollow" class="external text" href="https://web.archive.org/web/20170706124808/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1666.pdf">Nagpal</a>). Multiple gradients are formed and used to form a coordinate system via triangulation.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Researchers_and_labs">Researchers and labs</h2></div>

<ul><li><a href="Hal_Abelson" title="Hal Abelson">Hal Abelson</a>, MIT</li>

<li><a rel="nofollow" class="external text" href="http://web.mit.edu/jakebeal/www/">Jacob Beal</a>, graduate student MIT (high level languages for amorphous computing)</li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20071111024514/http://www.mona.uwi.edu/fpas/isconf/5.htm">Daniel Coore</a>, University of West Indies (growing point language, tropism, grown inverter series)</li>

<li><a href="Nikolaus_Correll" title="Nikolaus Correll">Nikolaus Correll</a>, University of Colorado (<a href="Robotic_materials" title="Robotic materials">robotic materials</a>)</li>

<li><a href="Tom_Knight_(scientist)" title="Tom Knight (scientist)">Tom Knight</a>, MIT (computation with synthetic biology)</li>

<li><a rel="nofollow" class="external text" href="http://www.eecs.harvard.edu/~rad/">Radhika Nagpal</a>, Harvard (self-organizing systems)</li>

<li>Zack Booth Simpson, Ellington Lab, Univ. of Texas at Austin. (Bacterial edge detector)</li>

<li><a href="Gerry_Sussman" class="mw-redirect" title="Gerry Sussman">Gerry Sussman</a>, MIT AI Lab</li>

<li><a rel="nofollow" class="external text" href="http://groups.csail.mit.edu/synbio/">Ron Weiss</a>, MIT (rule triggering, microbial colony language, coli pattern formation)</li></ul>

<ul><li><a href="Unconventional_computing" title="Unconventional computing">Unconventional computing</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Documents">Documents</h2></div>

<ol><li><a rel="nofollow" class="external text" href="http://www-swiss.ai.mit.edu/projects/amorphous/">The Amorphous Computing Home Page</a>

<dl><dd>A collection of papers and links at the MIT AI lab</dd></dl></li>

<li><a rel="nofollow" class="external text" href="http://www-swiss.ai.mit.edu/projects/amorphous/cacm-2000.html">Amorphous Computing (Communications of the ACM, May 2000)</a>

<dl><dd>A review article showing examples from Coore's Growing Point Language as well as patterns created from Weiss's rule triggering language.</dd></dl></li>

<li><a rel="nofollow" class="external text" href="https://dx.doi.org/10.1016/j.biosystems.2014.09.010">"Amorphous computing in the presence of stochastic disturbances"</a>

<dl><dd>A paper investigating the ability of Amorphous computers to deal with failing components.</dd></dl></li>

<li><a rel="nofollow" class="external text" href="http://www-swiss.ai.mit.edu/projects/amorphous/tucson-talk/">Amorphous Computing Slides from DARPA talk in 1998</a>

<dl><dd>An overview of ideas and proposals for implementations</dd></dl></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20060930210914/http://isandtcolloq.gsfc.nasa.gov/fall2002/presentations/abelson.ppt">Amorphous and Cellular Computing PPT from 2002 NASA Lecture</a>

<dl><dd>Almost the same as above, in PPT format</dd></dl></li>

<li><a rel="nofollow" class="external text" href="http://people.csail.mit.edu/jrb/stp/proto-isys-2006.pdf">Infrastructure for Engineered Emergence on Sensor/Actuator Networks</a>, Beal and Bachrach, 2006.

<dl><dd>An amorphous computing language called "Proto".</dd></dl></li>

<li><a rel="nofollow" class="external text" href="http://www-swiss.ai.mit.edu/projects/amorphous/Robust/laurenc/amorphous/">Self-repairing Topological Patterns</a> Clement, Nagpal.

<dl><dd>Algorithms for self-repairing and self-maintaining line.</dd></dl></li>

<li><a rel="nofollow" class="external text" href="http://www-swiss.ai.mit.edu/projects/amorphous/Robust/joshuag/">Robust Methods of Amorphous Synchronization</a>, Joshua Grochow

<dl><dd>Methods for inducing global temporal synchronization.</dd></dl></li>

<li><a rel="nofollow" class="external text" href="http://www.swiss.ai.mit.edu/projects/amorphous/Progmat/">Programmable Self-Assembly: Constructing Global Shape Using Biologically-Inspired Local Interactions and Origami Mathematics</a> and <a rel="nofollow" class="external text" href="http://www.swiss.ai.mit.edu/projects/amorphous/Progmat/talk/img0.htm">Associated Slides</a> Nagpal PhD Thesis

<dl><dd>A language to compile local-interaction instructions from a high-level description of an origami-like folded structure.</dd></dl></li>

<li><a rel="nofollow" class="external text" href="http://www-swiss.ai.mit.edu/projects/amorphous/Progmat/thesis/activecells.html">Towards a Programmable Material</a>, Nagpal <a rel="nofollow" class="external text" href="http://swiss.csail.mit.edu/projects/amorphous/Progmat/thesis/old-talk/">Associated Slides</a>

<dl><dd>Similar outline to previous paper</dd></dl></li>

<li><a rel="nofollow" class="external text" href="http://www-swiss.ai.mit.edu/~zucker/paper/">Self-Healing Structures in Amorphous Computing</a> Zucker

<dl><dd>Methods for detecting and maintaining topologies inspired by biological regeneration.</dd></dl></li>

<li><a rel="nofollow" class="external text" href="http://www.csail.mit.edu/~jrb/Projects/rseam.pdf">Resilient serial execution on amorphous machines</a>, Sutherland Master's Thesis

<dl><dd>A language for running serial processes on amorphous computers</dd></dl></li>

<li><a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/cache/papers/cs/2546/http:zSzzSzswissnet.ai.mit.eduzSz~switzzSzamorphouszSzpaperszSzaimemo1614.pdf/coore97paradigms.pdf">Paradigms for Structure in an Amorphous Computer</a>, 1997 Coore, Nagpal, Weiss

<dl><dd>Techniques for creating hierarchical order in amorphous computers.</dd></dl></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20170706124808/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1666.pdf">Organizing a Global Coordinate System from Local Information on an Amorphous Computer</a>, 1999 Nagpal.

<dl><dd>Techniques for creating coordinate systems by gradient formation and analyzes precision limits.</dd></dl></li>

<li><a rel="nofollow" class="external text" href="https://www.scribd.com/doc/161011637/AMORPHOUOS-COMPUTING-Examples-Mathematics-and-Theory-August2013">Amorphous Computing: examples, mathematics and theory</a>, 2013 W Richard Stark.

<dl><dd>This paper presents nearly 20 examples varying from simple to complex, standard mathematical tools are used to prove theorems and compute expected behavior, four programming styles are identified and explored, three uncomputability results are proved, and the computational foundations of a complex, dynamic intelligence system are sketched.</dd></dl></li></ol></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-16" href="https://en.wikipedia.org/wiki/?title=Amorphous_computing&oldid=1290639550">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>